import java.util.HashMap;
import java.util.Map;

class Solution {
    // 暴力枚举
    // public int[] twoSum(int[] nums, int target) {
    //     int[] ret = new int[2];
    //     // 固定一个数，往前找是否有符合的
    //     for (int i = 1; i < nums.length; i++) {
    //         int t = target - nums[i];
    //         for (int j = i-1; j >= 0; j--) {
    //             if (t == nums[j]) {
    //                 ret[0] = i;
    //                 ret[1] = j;
    //                 break;
    //             }
    //         }
    //     }
    //     return ret;
    // }


    // 哈希表优化
    public int[] twoSum(int[] nums, int target) {
        int[] ret = new int[2];
        Map<Integer, Integer> hash = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int t = target - nums[i]; // i 的位置已经确定得找到 j 的位置
            // 看看哈希表中是否存在j的值
            if (hash.get(t) != null) {
                ret[0] = i;
                ret[1] = hash.get(t);
                return ret;
            }
            hash.put(nums[i], i); // 将当前数值 与 下标存放到哈希表中
        }
        return ret;
    }


    // 暴力哈希表
    public int[] twoSum2(int[] nums, int target) {
        int[] ret = new int[2];
        Map<Integer, Integer> hash = new HashMap<>();
        // 初始化哈希表
        for (int i = 0; i < nums.length; i++) {
            hash.put(nums[i], i);
        }
        // 寻找两数之和
        for (int i = 0; i < nums.length; i++) {
            // 得排除是相同下标的情况
            if (hash.get(target - nums[i]) != null && hash.get(target - nums[i]) != i) {
                ret[0] = i;
                ret[1] = hash.get(target - nums[i]);
                return ret;
            }
        }
        return ret;
    }
}